Базовые понятия о связности

**Маршрутом** в графе называется последовательность вершин и ребер: $v_0 e_1 v_1 e_2 v_2 \dots e_{k-1} v_k$, где $e_i$ соединяет вершины $v_i$ и $v_{i+1}$. Часто пишут $(v_0, v_k)$ — маршрут. Если граф обыкновенный (без кратных ребер), то маршрут задается однозначно последовательностью вершин.

**Длина маршрута** — число ребер.

Маршрут, в котором нет повторяющихся ребер, называется **цепью**. Если нет ни повторяющихся ребер, ни вершин, то он называется **простой цепью (путем)**.

**Циклом** называется маршрут, в котором совпадают концевые вершины. **Простой цикл** — это цикл, в котором все вершины различны, кроме концевых.

Вершины $v$ и $w$ называются **связанными**, если в графе есть $(v,w)$ — маршрут.

Граф называется **связным**, если между любой парой вершин есть маршрут.

Отношение связанности в графе является отношением эквивалентности. Классы эквивалентности данного отношения — **компоненты связности**.